package com.aqie.medium.sort;

import com.aqie.easy.structure.ListNode;

/**
 * 148 排序链表
 * TODO
 *
 */
public class SortList {
    /**
     * 归并排序
     * 1.分割cut环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归时可以处理正确的链表片段）；
     *      我们使用fast,slow快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
     *      找到中点slow后，执行slow.next = None将链表切断。
     *      递归分割时，输入当前链表左端点head和中心节点slow的下一个节点tmp(因为链表是从slow开始切断的)。
     *      递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
     * 2,合并merge环节： 将两个排序链表合并，转化为一个排序链表。
     *      双指针法合并，时间复杂度O(l + r)，l, r分别代表两个链表长度。
     * 3,当head == None时，直接返回None。
     **/
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }


    /**
     * 快速排序
     * @param head
     * @return
     */
    public ListNode sortList2(ListNode head) {
        quickSort(head,null);
        return head;
    }
    public void quickSort(ListNode head,ListNode end){
        if(head!=end && head.next!=end){
            ListNode q=partition(head,end);
            quickSort(head,q);
            quickSort(q.next,end);
        }
    }
    public ListNode partition(ListNode head,ListNode end){
        ListNode p=head;
        ListNode cur=head.next;
        int key=head.val;
        while(cur!=end){
            if(cur.val<=key){
                p=p.next;
                int tmp=p.val;
                p.val=cur.val;
                cur.val=tmp;
            }
            cur=cur.next;
        }
        int tmp=head.val;
        head.val=p.val;
        p.val=tmp;
        return p;

    }
}
